package leetcode;

import leetcode.N094BinaryTreeInorderTraversal.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author yinlei
 * @date 2018/6/27
 * @since 1.0.0
 */
public class N102BinaryTreeLevelOrderTraversal {

    public static void main(String[] args) {

        System.out.println(levelOrder(array2Tree()));
    }

    private static TreeNode array2Tree() {
        TreeNode root = new TreeNode(1);

        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        return root;
    }
    static public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();

        List<List<Integer>> result = new ArrayList<>();

        List<TreeNode> level = new ArrayList<>();
        level.add(root);

        while (level.size() > 0) {

            List<TreeNode> next = new ArrayList<>();
            List<Integer> levelResult = new ArrayList<>();

            for (TreeNode item : level) {
                levelResult.add(item.val);

                if (item.left != null) {
                    next.add(item.left);
                }
                if (item.right != null) {
                    next.add(item.right);
                }
            }

            result.add(levelResult);
            level = next;
        }

        return result;
    }
}
